Quick Sort
Sorting is the process of arranging elements in either ascending or descending order. One common sorting algorithm is Quick Sort, which works on the Divide and Conquer strategy. Quick Sort recursively partitions the given array into right and left halves and sorts each partition using a pivot element. The array elements are rearranged such that elements smaller than the pivot are on the left, while elements greater than the pivot are on the right. This process is repeated for each partition until the entire array is sorted.
Here are the key steps:
- Pivot Element: The first element is selected as the pivot. The Quick Sort algorithm places the pivot element in its final position within the sorted array.
- Partition: The pivot element divides the array into two parts, a process known as partitioning. After partitioning, the pivot is positioned correctly in the final sorted order.
Video Lecture
Quick Sort Operation
Unlike merge sort, quick sort divides the array into two subarrays based on a pivot value. The sizes of the two subarrays need not be equal, they may be either equal or unequal.
Partition: The split point S represents the final location of the pivot element. It splits the array into two parts: all elements before the pivot element A[S] are less than or equal to the pivot element, and all elements after A[S] are greater than or equal to the pivot element.
.png)
.png)
.png)
Algorithm
QuickSort(A[0]..A[n-1])
Input: Unsorted Array A containing n elements.
Output: Sorted Array A.
Step 1: Start.
Step 2: If the array has one or zero elements (n <= 1), it is already sorted. Return.
Step 3: Choose a pivot element from the array. (Typically, the first, last, or middle element)
Step 4: Partition the array into three parts:
Left Partition:Elements less than the pivot.Pivot:The pivot element itself.Right Partition:Elements greater than the pivot.
Step 5: Recursively apply QuickSort to the left partition.
Step 6: Recursively apply QuickSort to the right partition.
Step 7: Combine the sorted left partition, the pivot, and the sorted right partition into a single array.
Step 8: Output the sorted array.
Step 9: Stop.
Binary Search Code
#include <stdio.h>
// Function prototypes
void InputArray(int arr[], int n);
void swap(int *a, int *b);
int partition(int arr[], int low, int high);
void quickSort(int arr[], int low, int high);
int main() {
int arr[100], n;
printf("Enter the size of the array \n");
scanf("%d", &n);
InputArray(arr, n);
// printing the original array
printf("Original array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
// calling quickSort() to sort the given array
quickSort(arr, 0, n - 1);
// printing the sorted array
printf("\nSorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
// Function to input elements into the array
void InputArray(int arr[], int n) {
printf("Enter %d elements of the array:\n", n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
}
// Function to swap two elements
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Function to partition the array
int partition(int arr[], int low, int high) {
int pivot = arr[low];
int i = low;
int j = high;
while (i < j) {
while (arr[i] <= pivot && i <= high - 1) {
i++;
}
while (arr[j] > pivot && j >= low + 1) {
j--;
}
if (i < j) {
swap(&arr[i], &arr[j]);
}
}
swap(&arr[low], &arr[j]);
return j;
}
// Function to perform quicksort on the array
void quickSort(int arr[], int low, int high) {
if (low < high) {
int partitionIndex = partition(arr, low, high);
quickSort(arr, low, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, high);
}
}
#include <iostream>
using namespace std;
// Function to swap two elements
void swap(int &a, int &b) {
int temp = a;
a = b;
b = temp;
}
// Partition function for Quick Sort
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return (i + 1);
}
// Quick Sort function
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Function to print the array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout < arr[i] < " ";
cout < endl;
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
cout < "Sorted array: ";
printArray(arr, n);
return 0;
}
public class QuickSort {
// Function to swap two elements
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Partition function for Quick Sort
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return (i + 1);
}
// Quick Sort function
private static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Function to print the array
private static void printArray(int[] arr) {
for (int value : arr) {
System.out.print(value + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
quickSort(arr, 0, arr.length - 1);
System.out.println("Sorted array:");
printArray(arr);
}
}
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
# Example usage
arr = [10, 7, 8, 9, 1, 5]
sorted_arr = quick_sort(arr)
print("Sorted array:", sorted_arr)
Analysis of Quick Sort
Time Complexity
In Merge Sort, the recursive process creates a tree of height log n, and there are log n + 1 levels in this tree. At each level, the algorithm performs a maximum of n comparisons. The total number of comparisons across all levels is the sum of comparisons at each level, resulting in a total of n.log n comparisons. Therefore, the time complexity is T(n) = n.log n = O(n.log n).
The basic operation of the Merge Sort algorithm is comparison. The time complexity is determined by how many times this comparison operation is performed. The running time T(n) for an input of size n is the sum of the time taken to divide the array into subarrays until we reach single elements and the time taken to sort and merge the sorted arrays.
Best Case: If the array is already sorted, the algorithm performs a minimum number of comparisons.
Worst Case: The worst-case scenario occurs during the sort and merge operations, particularly when elements are taken alternately from the two sorted input arrays. Merge Sort performs the maximum number of comparisons in this case.
Given that T(n) is the time taken to sort n elements using Merge Sort, the recurrence relation for Merge Sort is:
T(n) = T(n/2) + Tmerge(n)
Where Tmerge(n) is the time taken for the merge operation. In the worst case, the merge operation takes n-1 comparisons, so:
Tmerge(n) = n-1
Thus, the worst-case time complexity for Merge Sort is:
Tworst(n) = Tworst(n/2) + Tmerge(n)
Tworst(n) = Tworst(n/2) + (n-1)
According to the Master Theorem, Tworst(n/2) = n.log n, so:
Tworst(n) = n.log n + (n-1)
Tworst(n) = n.log n
Tworst(n) = O(n.log n)
Space Complexity
In the merge phase, elements from the two subarrays are copied into a newly created array. During the final merge step, the extra array size equals the input array size. Since the Merge Sort algorithm requires an additional array of size n for storing the n elements, the space complexity of Merge Sort is O(n).
.png)
